package org.lql.algo.codecrush.hot100.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-31 11:02
 * @description: 46. 全排列 <a href="https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Permute {

	int n;
	boolean[] used;
	List<Integer> range = new ArrayList<>();
	List<List<Integer>> ans = new ArrayList<>();

	public List<List<Integer>> permute(int[] nums) {
		n = nums.length;
		used = new boolean[n];
		recur(nums, 0);
		return ans;
	}

	public void recur(int[] nums, int pos) {
		// 递归终止条件
		if (pos == n) {
			ans.add(new ArrayList<>(range));
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!used[i]) {
				// 将当前数字加入排列中，并标记为已使用
				range.add(nums[i]);
				used[i] = true;
				// 递归调用下一个位置：选择一个未使用的数字
				recur(nums, pos + 1);
				// 恢复现场，将当前数字从排列中移除，并标记为未使用
				used[i] = false;
				range.remove(range.size() - 1);
			}
		}
	}

	public static void main(String[] args) {
		Permute permute = new Permute();
		System.out.println(permute.permute(new int[]{1, 2, 3}));
	}
}
